package org.rescue.analysis.InterCollection;

import java.util.Enumeration;
import java.util.Vector;

import javax.swing.tree.DefaultMutableTreeNode;

import org.rescue.Dag.Concept;
import org.rescue.Dag.DAGNode;
import org.rescue.Dag.DirectedAcyclicGraph;

public class GreedyCDiff {
	double totalCard1;
	double totalCard2;

	public DefaultMutableTreeNode compare (DirectedAcyclicGraph t, Concept rootConcept, int totalCard1, int totalCard2, int k) {
		this.totalCard1 = totalCard1;
		this.totalCard2 = totalCard2;
		Enumeration<DAGNode> nodes = t.postOrder(rootConcept);
		while (nodes.hasMoreElements()) {
			DAGNode cnode = nodes.nextElement();
			//	get one created during tree formation
			Concept con = cnode.getNodeConcept();

			/* Add self in candidates tree  */
			DefaultMutableTreeNode cand = new DefaultMutableTreeNode();
			CCandidateData candData = new CCandidateData();
			candData.id = con.id;
			candData.dCard1 = con.dCard;
			candData.card1 = con.card;
			candData.dCard2 = ((CAuxiliaryData)con.getAuxData()).dCard;
			candData.card2 = ((CAuxiliaryData)con.getAuxData()).card;
			candData.isCand = false;
			candData.includeInCand = false;
			cand.setUserObject(candData);			
			((CAuxiliaryData)con.getAuxData()).setCandTree(cand);

			// use cardinality set by TaxonomyReader to recursively compute parent cardinality
			con.card += con.dCard; // initialized card
			if (!cnode.isRoot()) { 
				Vector<Concept> pars = t.getParents(con);
				for (int i = 0; i < pars.size(); i++) {
					pars.elementAt(i).card += con.card;
					//System.out.println(con.id + " par card " + pars.elementAt(i).card);
				}
			}

			if (!cnode.isLeaf()) 
			{
				/* Growing phase */	
				/* Populate node's cand tree with all the candidates from all of its children;
					The candidate node being added may in turn has its own
					children which remain linked with the node. */

				for (int i = 0; i < cnode.getChildCount(); i++) 
				{
					Concept childCon = cnode.getChildAt(i).getNodeConcept();

					// since we do not remove zero-cardinality concepts 
					if (childCon.card > 0) {
						//System.out.println(childCon.id);
						DefaultMutableTreeNode childCand = ((CAuxiliaryData) childCon.getAuxData()).getCandTree(); 
						// make candtrees of all childConcepts children of candNode
						cand.add(childCand);
						CCandidateData childCandData = (CCandidateData)childCand.getUserObject();

						// can include the child in candidates
						childCandData.includeInCand = true;
						if (!childCandData.isCand) {
							candData.subCandsCount = candData.subCandsCount + childCandData.subCandsCount + 1;
						}
						else {
							candData.subCandsCount += childCandData.subCandsCount;
						}
					}
				}

				/* Merging Phase */
				/* During merging, do a postorder traversal of the candidate tree of each child and
				 * compute information loss of a meerge. 
				 * NOTE: the child cand concept is merged with the current parent cand concept
				 * if it's candidate subtree is empty and the child node is the only one left.
				 * */

				if (candData.subCandsCount <= k ) 
					continue;  // no need to merge, so continue postorder
				else 
				{
					while (candData.subCandsCount > k) 
					{
						CMinLossData minLossData, newMinLossData;
						minLossData = new CMinLossData(Double.POSITIVE_INFINITY);
						for (int j = 0; j < cand.getChildCount(); j++) 
						{ 
							System.out.println("visting under " + candData.id + " " 
									+ ((CCandidateData)((DefaultMutableTreeNode)cand.getChildAt(j)).getUserObject()).id);

							// consider merging one node
							newMinLossData = findMinLossMerge ((DefaultMutableTreeNode)cand.getChildAt(j));
							if (newMinLossData.getMinloss() < minLossData.getMinloss() ) 
							{
								minLossData = newMinLossData;
							}
						}
						System.out.println("meging " +
								((CCandidateData)minLossData.getMergeParent().getUserObject()).id
								+ " -> " +
								((CCandidateData)minLossData.getMergeChild().getUserObject()).id 
								+ "  " + minLossData.minloss);

						merge (minLossData); // merge and recomputes cardinality of candidate tree

						// if not already discounted
						if (((CCandidateData)((DefaultMutableTreeNode)minLossData.getMergeParent()).getUserObject()).id !=
							candData.id)
							candData.subCandsCount -= 1;
					}
				}
			}
			else {
				// make self a cand
				candData.subCandsCount = 1;
				candData.isCand = true;
			}
		}
		return ((CAuxiliaryData)rootConcept.getAuxData()).getCandTree();
	}

	public CMinLossData findMinLossMerge(DefaultMutableTreeNode childCand) {
		double loss;
		DefaultMutableTreeNode mergeParent;
		DefaultMutableTreeNode mergeChild;
		CMinLossData minLossData = new CMinLossData(Double.POSITIVE_INFINITY);
		Enumeration e = childCand.postorderEnumeration();

		while (e.hasMoreElements()) {
			mergeChild = (DefaultMutableTreeNode)e.nextElement();
			CCandidateData mergeChildData = (CCandidateData)mergeChild.getUserObject();

			if (mergeChildData.id == ((CCandidateData)childCand.getUserObject()).id
					&& !mergeChild.isLeaf()) { // since leaves are cands automatically
				if (mergeChildData.isCand) {
					loss = computeLoss(mergeChildData);
					minLossData.setChildCandNode(childCand);
					minLossData.setMergeChild(mergeChild);
					minLossData.setMergeParent(mergeChild);
					minLossData.setMinloss(loss);
				}
			}
			else {
				mergeParent = (DefaultMutableTreeNode) mergeChild.getParent(); 
				CCandidateData mergeParentData = (CCandidateData)mergeParent.getUserObject();
				loss = computeLoss(mergeChildData);
				//System.out.println(mergeChildData.id + " to " + mergeParentData.id + " " + loss);

				if ( loss < minLossData.getMinloss()) {
					// populate minLossData with new data
					minLossData.setChildCandNode(childCand);
					minLossData.setMergeChild(mergeChild);
					minLossData.setMergeParent(mergeParent);
					minLossData.setMinloss(loss);
				}
			}
		}	

		return minLossData; 
	}

	public void merge (CMinLossData minLossData) {
		DefaultMutableTreeNode mergeChild = minLossData.getMergeChild();
		DefaultMutableTreeNode mergeParent = minLossData.getMergeParent();

		// (1) update minLossData.mergeParent.direcCardinality
		CCandidateData mergeParentData = (CCandidateData) mergeParent.getUserObject();
		CCandidateData mergeChildData = ((CCandidateData)mergeChild.getUserObject());

		// removing self from candidate set
		if (mergeParentData.id == mergeChildData.id) {
			mergeParentData.isCand = false;
			mergeParentData.subCandsCount -= 1;	
		}		
		else {
			mergeParentData.dCard1 = mergeParentData.dCard1 + mergeChildData.dCard1;		
			mergeParentData.dCard2 = mergeParentData.dCard2 + mergeChildData.dCard2;

			// (2) making children of minLossData.mergeChild children of minLossData.mergeParent
			while (mergeChild.getChildCount() > 0)
			{
				DefaultMutableTreeNode grandchildCand = (DefaultMutableTreeNode)mergeChild.getFirstChild();
				mergeParent.add(grandchildCand); // also removes grandchildCand from mergeChild.
				// due to one node one parent requirement
			}
			// (3) removing minLossData.mergeChild
			mergeChild.removeFromParent();

			if (!mergeParentData.includeInCand || mergeParentData.isCand) 
				mergeParentData.subCandsCount -= 1;
			else { // cand size not yet reduced
				mergeParentData.isCand = true;
			}
		}
	}
	/**
	 * 
	 * @param childcard
	 * @param parentcard
	 * @param distance is the distance between the two merged concepts
	 * @return
	 */

	public double log2(double d) {
		return Math.log(d)/Math.log(2.0);
	}

	public double computeLoss(CCandidateData mergeChildCandData) {
		//double loss = Double.POSITIVE_INFINITY;
		double loss = 0.0;
		// loss = mergeChildCandData.getInfoLoss(); // zero for leaf concepts
		double childP1 = (double) (mergeChildCandData.dCard1) / totalCard1;
		double childP2 = (double) (mergeChildCandData.dCard2) / totalCard2;

		double KL1 = (childP1 * log2(childP1/childP2)) 
		+ ((1-childP1) * log2((1-childP1)/(1-childP2)));

		double KL2 = (childP2 * log2(childP2/childP1)) 
		+ ((1-childP2) * log2((1-childP2)/(1-childP1)));

		loss = (0.5)*(KL1 + KL2);		

		System.out.println("select " + mergeChildCandData.id + "with merge loss: " + loss);
		return loss;
	}
}


/*
double newParentP1 = (double) (mergeAncestorCandData.dCard1 + mergeChildCandData.dCard1) / totalCard1;
double newParentP2 = (double) (mergeAncestorCandData.dCard2 + mergeChildCandData.dCard2) / totalCard2;

double KL1 = (newParentP1 * log2(newParentP1/newParentP2)) 
			+ ((1-newParentP1) * log2((1-newParentP1)/(1-newParentP2)));

double KL2 = (newParentP2 * log2(newParentP2/newParentP1)) 
			+ ((1-newParentP2) * log2((1-newParentP2)/(1-newParentP1)));

loss = (0.5)*(KL1 + KL2);
*/
